#include <bits/stdc++.h>
#ifndef DEBUG
#define debug
#endif
using namespace std;
using i64 = int64_t;

const int mod = 1e9;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  string s;
  cin >> s;
  int n = s.size();
  vector<vector<i64>> dp(n, vector<i64>(n, 0));
  for (int l = n - 1; l >= 0; l --) {
    dp[l][l] = 1;
    for (int r = l + 1; r < n; r ++) {
      if (s[l] != s[r]) continue;
      for (int k = l; k < r; k ++) {
        if (s[k] == s[r]) {
          dp[l][r] = (dp[l][r] + dp[l][k] * dp[k + 1][r - 1] % mod) % mod;
        }
      }
    }
  }
  cout << dp[0][n - 1] << endl;
}